//
// Created by Administrator on 2024-2-19
// 分大于,小于等于区 以最后一个数字为准
//

#include <iostream>
#include <vector>
#include "arrUtil.h"

using namespace std;

int netherlands(vector<int> &vector, int l, int r);
void quick_sort(vector<int> &v, int l, int r);

int main()
{
    vector<int> arr = {7, 2, 9, 3, 6, 3, 6, 5, 4};
//    arr={7,6,5,9,6};
//    arr={5,6};
//    arr={2,3,3};
//    arr={2,3};
//    arr={2};
    randVector(arr,1000);
    quick_sort(arr, 0, arr.size() - 1);
//    cout<<netherlands(arr, 0, arr.size() - 1)<<endl;
//    printVector(arr);
    cout<<checkSortVector(arr);
    return 0;
}

void quick_sort(vector<int> &v, int l, int r){
    if (l>=r)
        return;
    int m = netherlands(v,l,r);
    quick_sort(v,l,m-1);
    quick_sort(v,m+1,r);
}

int netherlands(vector<int> &v, int l, int r)
{
    int cur = v[r];
    int less_equal= l-1; //小于等于区的右边界
    for (int i = l; i <r ; ++i)
    {
         if(v[i]<=cur)
         {
             swap(v[i],v[less_equal+1]);
             less_equal++;
         }
    }
    swap(v[less_equal+1],v[r]);
//    printVector(v);
//    cout<<less_equal+1<<endl;
    return less_equal+1;
}
